/**
 * 117. 填充每个节点的下一个右侧节点指针 II
 * https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/
 */
public class Solutions_117 {
    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right = new Node(3);
        root.right.right = new Node(7);  // output: {1, #, 2, 3, #, 4, 5, 7, #}

        Node result = connect(root);
        System.out.println(result);
    }

    /**
     *         1      (1, null)
     *       /  \
     *      2    3     (2, 3, null)
     *     /    / \
     *    4    5   6    (4, 5, 6, null)
     *   /        / \
     *  7        8  9    (7, 8, 9, null)
     *  填充的方式只能两种：
     *  1. 左子节点不为 null 且右子节点不为 null，那么将右子节点作为左子节点的 next
     *  2. 左子节点不为 null 且右子节点为 null（右子节点不为 null） 的情况，都需要递归父节点的 next 来获取
     *  以 7 为例，next 节点是 8，代码逻辑为先查找 4.next 的左右子节点，而 5 没有节点，那么再找 5.next，结果就是 6 的左子节点 8
     */
    public static Node connect(Node root) {
        if (root == null) {
            return null;
        }
        if (root.left != null) {
            if (root.right != null) {
                // 右子节点不为 null 时，左子节点的右侧节点就是 root.right
                root.left.next = root.right;
            } else {
                // 右子节点为 null 时，左子节点的右侧节点只能通过父节点的 next 节点来获取
                root.left.next = getNext(root.next);
            }
        }
        if (root.right != null) {
            // 右子节点的右侧节点只能通过父节点的 next 节点来获取
            root.right.next = getNext(root.next);
        }
        // 因为是要找每个节点的右侧节点，那么就需要先遍历右子树，计算得到 root.next
        // 因为左子树中的每个左子节点，若兄弟节点（右子节点）为 null 时，那么就需要通过 root.next（根节点的右侧节点） 来计算右侧节点
        connect(root.right);
        connect(root.left);
        return root;
    }

    /**
     * 根据当前父节点（root）的 next 节点来获得当前节点的右侧节点
     * 1. root.next 节点的左子节点不为 null 时，当前节点的右侧节点就是 root.next 的左子节点
     * 2. root.next 节点的左子节点为 null，而右子节点不为 null 时，当前节点的右侧节点就是 root.next 的右子节点
     * 3. root.next 节点的左、右子节点都为 null 时，递归进入 root.next.next，重复步骤 1
     */
    public static Node getNext(Node root) {
        if (root == null) {
            return null;
        }
        if (root.left != null) {
            return root.left;
        }
        if (root.right != null) {
            return root.right;
        }
        return getNext(root.next);
    }
}


